package com.cty._05_Ability._56_01_NumbersAppearOnce;

/**
 * @Auther: cty
 * @Date: 2020/7/22 19:58
 * @Description: 面试题56（一）：数组中只出现一次的两个数字
 * 题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序
 * 找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 * @version: 1.0
 */
public class NumbersAppearOnce {

    private static int num1;
    private static int num2;

    public static void printNumbersAppearOnce(int[] array){
        num1 = 0;
        num2 = 0;
        numbersAppearOnce(array);
        if(num1==num2)
            return;
        System.out.println("数组中只出现一次的两个数字为：" + num1 + "、" + num2);
    }

    private static void numbersAppearOnce(int[] array){
        if(array==null || array.length<2)
            return;

        // 全部异或
        int resultOfOR = 0;
        for(int i=0; i<array.length; i++)
            resultOfOR ^= array[i];

        int indexOf1 = findFirstBitIs1(resultOfOR);
        if(indexOf1 == 32)
            return;

        for(int i=0; i<array.length; i++){
            if(isBit1OfTheIndex(array[i], indexOf1))
                num1 = num1^array[i];
            else
                num2 = num2^array[i];
        }

    }  // end numbersAppearOnce()

    // 查找数字num从右边开始第一次出现1的位的索引
    private static int findFirstBitIs1(int num){
        int indexBit = 0;
        while(((num&1)==0) && (indexBit<32)){
            num = num>>1;
            indexBit++;
        }
        return indexBit;
    }  // end findFirstBitIs1()

    // 判断数字num的第index位是否为1
    private static boolean isBit1OfTheIndex(int num, int index){
        num = num >> index;
        return (num&1) == 1;
    }  // end isBit1OfTheIndex()

}  // end class
